

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public class LinkedList {

    public ListNode head = new ListNode(-1);//指向双向链表的头节点
    public ListNode last;//指向的是尾巴节点

// 带头
    public void display() {
//和单链表的打印方式是一样
        if(this.head.next==null){
            return;
        }
        ListNode head1 = this.head.next;
        ListNode cur = head1;
        while (cur != null) {
            System.out.print(cur.val +" ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 不带头
//    public void display() {
////和单链表的打印方式是一样
//        ListNode cur = this.head;
//        while (cur != null) {
//            System.out.print(cur.val +" ");
//            cur = cur.next;
//        }
//        System.out.println();
//    }

    //得到单链表的长度
    // 带头的
    public int size() {
        if(this.head.next==null){
            return 0;
        }
        int count = 0;
        ListNode cur = this.head.next;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    // 不带头
//    public int size() {
//        int count = 0;
//        ListNode cur = this.head;
//        while (cur != null) {
//            count++;
//            cur = cur.next;
//        }
//        return count;
//    }

    //查找是否包含关键字key是否在单链表当中
    // 带头的
    public boolean contains(int key) {
        if(this.head.next==null){
            return false;
        }
        ListNode cur = this.head.next;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    // 不带头的
//    public boolean contains(int key) {
//        ListNode cur = this.head;
//        while (cur != null) {
//            if (cur.val == key) {
//                return true;
//            }
//            cur = cur.next;
//        }
//        return false;
//    }

    //头插法
    // 带头的
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head.next == null){
            this.head.next = node;
            node.prev = head;
            this.last = node;
        }else{
            node.next = this.head.next;
            node.prev = this.head;
            this.head.next = node;
        }
    }

    // 不带带头的
//    public void addFirst(int data) {
//        ListNode node = new ListNode(data);
//        if (this.head == null) {
//            this.head = node;
//            this.last = node;
//        } else {
//            node.next = this.head;
//            this.head.prev = node;
//            this.head = node;
//        }
//    }

    //尾插法
    // 带头的
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(this.head.next == null){
            this.head.next = node;
            node.prev = head;
            this.last = node;
            return;
        }
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }

    // 不带头的：
//    public void addLast(int data) {
//        ListNode node = new ListNode(data);
//        if (this.head == null) {
//            this.head = node;
//            this.last = node;
//            return;
//        }
//        last.next = node;
//        node.prev = last;
//        last = node;
//    }

    //任意位置插入,第一个数据节点为0号下标
    // 带头的
    public void addIndex(int index, int data) {
        if(index<0||index>size()){
            System.out.println("index 位置不合法");
            return ;
        }
        ListNode node = new ListNode(data);
        if(index == 0){
            addFirst(data);
            return ;
        }
        if (index == size()){
            addLast(data);
            return ;
        }
        ListNode cur = searchIndex(index);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next =node;
        cur.prev = node;
    }
    public  ListNode searchIndex(int index){
        ListNode cur = this.head.next;
        while(index!=0){
            cur = cur.next;
            index--;
        }
        return cur;
    }


    // 不带头的
//    public void addIndex(int index, int data) {
//        if(index<0||index>size()){
//            System.out.println("index 位置不合法");
//            return ;
//        }
//        ListNode node = new ListNode(data);
//        if(index == 0){
//            addFirst(data);
//            return ;
//        }
//        if (index == size()){
//            addLast(data);
//            return ;
//        }
//        ListNode cur = searchIndex(index);
//        node.next = cur;
//        node.prev = cur.prev;
//        cur.prev.next =node;
//        cur.prev = node;
//    }
//    public  ListNode searchIndex(int index){
//         ListNode cur = this.head;
//         while(index!=0){
//             cur = cur.next;
//             index--;
//         }
//         return cur;
//    }

    //删除第一次出现关键字为key的节点
    // 带头的
    public void remove(int key) {
        if (this.head.next == null) {
            return;
        }
        ListNode head1 = this.head.next;
        ListNode cur = head1;
        while (cur != null) {
            if (cur.val == key) {
                if (head1 == cur) {
                    if (cur.next == null) {
                        this.head.next = null;
                        this.last = this.head;
                    }else {
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = this.last.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }


    // 不带头的
//    public void remove(int key) {
//        if(this.head==null){
//            return;
//        }
//        ListNode cur  = this.head;
//        while(cur!=null){
//            if(cur.val==key){
//                if(this.head == cur){
//                    this.head = this.head.next;
//                    if(this.head !=null){
//                        this.head.prev = null;
//                    }else{
//                        this.last = null;
//                    }
//                } else{
//                    cur.prev.next = cur.next;
//                    if(cur.next!=null){
//                        cur.next.prev = cur.prev;
//                    }else{
//                        this.last = this.last.prev;
//                    }
//                }
//                return;
//            }
//            cur= cur.next;
//        }
//    }

    //删除所有值为key的节点
        // 带头的
    public void removeAllKey(int key) {
        if (this.head.next == null) {
            return;
        }
        ListNode head1 = this.head.next;
        ListNode cur = head1;
        while (cur != null) {
            if (cur.val == key) {
                if (head1 == cur) {
                    if (cur.next == null) {
                        this.head.next = null;
                        this.last = this.head;
                    }else {
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = this.last.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

        // 不带头的
//    public void removeAllKey(int key) {
//        if(this.head==null){
//            return;
//        }
//        ListNode cur  = this.head;
//        while(cur!=null){
//            if(cur.val==key){
//                if(this.head == cur){
//                    this.head = this.head.next;
//                    if(this.head !=null){
//                        this.head.prev = null;
//                    }else{
//                        this.last = null;
//                    }
//                } else{
//                    cur.prev.next = cur.next;
//                    if(cur.next!=null){
//                        cur.next.prev = cur.prev;
//                    }else{
//                        this.last = this.last.prev;
//                    }
//                }
////                return;
//            }
//            cur= cur.next;
//        }
//    }


    // 不带头
//    public void clear() {
//        while(this.head!=null){
//            ListNode headNext = this.head.next;
//            this.head.prev =null;
//            this.head.next = null;
//            this.head = headNext;
//        }
//        this.last = null;
//    }
//
//}
    // 带头
    public void clear() {
        if(this.head.next == null){
            this.last = null;
            this.head = null;
            return;
        }else {
            while(this.head.next!=null){
                ListNode headNext = this.head.next;
                this.head.prev =null;
                this.head.next = null;
                this.head = headNext;
            }
            this.last = null;
        }

    }

}